1. Field of the Invention
The present invention generally relates to a computer-based method for resource allocation and, more particulary, to a computer-based method for efficient use of scarce resources for improved productivity.
2. Description of the Related Art
A Linear Program is a widely used method of representing and approximating a solution to resource allocation problems arising in commerce and industry. As is known to one of skill in the art, a Linear Program utilizes what are defined as admissible values for a set of variables termed "decision variables" to form a set of constraints and, further, to measure by an objective function the quality of solution that is obtained.
Two well known methods for Linear Programs are the "Simplex Method" and the "Interior Point Method". The Simplex Method has been used for approximately five decades prior to the date of the present invention, while the Interior Point Method has been used since its development by N. Karmarker in 1984. In many commercial and industrial settings, however, there is a large volume of data, and a large number of variables and constraints which, in turn, cause each of these two methods to require very large computing resources. Such resources may be impractical or unavailable, which can render these two methods not usable for such settings. Therefore, for such cases, fast approximations methods which require less computing resources are needed.
A known method for such an approximation to Linear Programs is the "Subgradient Algorithm." The Subgradient Algorithm is well known in the art and can be found in various recognized and readily available treatises. The present invention is, however, directed to this Subgradient Algorithm and, accordingly, a summary description of that algorithm will be presented below for convenience. An algorithm flow-chart of the Subgradient Algorithm is on FIG. 1 of this description.
In the first step one accepts input information describing the physical system. The input data includes a matrix A and a vector b, both of which are used to set up the constraints of the system, a row of coefficients c used to measure the quality of a set of decisions x, and a plurality of bounds u, which are used to limit the acceptable values of x. The first step then, based on the above-described input information, forms the following Linear Program: ##EQU1##
The second step of the Subgradient Method forms a first approximation to the Linear Program by solving the following relaxed problem: ##EQU2## where .pi. is a set of parameters describing the importance of each constraint in A.
Under the commonly used terminology in the relevant art of linear programming, the components of the set n are called "dual variables," and the decision variables x are called "primal variables." A detailed discussion of these terms of art is not necessary for one of skill in the art to understand the present invention and, therefore, is omitted from this description. An interested reader can refer to any of several available textbooks such as, for example, G. B. Dantzig, "Linear Programming and Extensions", Princeton University Press (1963).
This second step requires as an input a first approximation to n which may, for example, be 0.
Solving the second step approximation is much easier, in terms of computational burden, than solving the original Linear Program of step one.
Let x denote the solution obtained at the end of step two. A third step then computes the following: EQU v=b-Ax (3)
The values in v are the violations of the original constraints.
Next, a fourth step updates the vector .pi. using the following formula: EQU .pi..rarw..pi.+.lambda.v. (4)
The parameter .lambda. is termed the "step size " and is generally set in a controllable manner by the operator. A standard method for the setting of .lambda. is: EQU .lambda.=f(1-Zu)/.parallel.v.parallel..sup.2 (5)
where f is a nonnegative value less than 2, Z.sub.u is an operator-specified upper bound for the minimum in Equation (1) based on a prior knowledge, if any, and .parallel.v.parallel..sup.2 =.SIGMA.v.sub.i.sup.2.
The Z.sub.u upper bound, if there is prior knowledge, represents a maximum cost, i.e., a maximum resource availability for the physical system that is modeled. For example, if the objective of the linear program is to minimize a transportation cost, but one million dollars is the maximum available money resource which cannot be exceeded, then the Z.sub.u upper bound is set at one million.
In the absence of prior knowledge, however, the operator may set an arbitrary high value for Z.sub.u.
As shown by FIG. 1, the Subgradient Method repeats by a main iteration loop steps two, three and four a number of times that is specified by the operator. As is well-known in the art of Linear Programming the number of iterations is specified in accordance with a predetermined maximum allowed discrepancy, the amount of computer resources that are available, and computing time limitations.
The known Subgradient Method produces a lower bound for the optimal value of cx in Equation (1) and a good approximation for the dual variables .pi.. A drawback of this Subgradient Method, though, is that it does not produce any approximation whatsoever to the parameters x, which are the parameters that describe the required optimal state of the physical system.